package com.leetcode.array;

import com.leetcode.annotation.Remark;

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.stream.Collectors;

/*
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

 

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
@Remark("二分查找和动态规划 - 寻找两个正序数组的中位数")
public class D_findMedianSortedArrays {
    public static void main(String[] args) {
        // int[] nums1 = {1, 3};
        // int[] nums2 = {4, 5, 6};
        // int[] nums1 = {};
        // int[] nums2 = {2, 3};

        // int[] nums1 = {10000};
        // int[] nums2 = {10001};

        // int[] nums1 = {10001};
        // int[] nums2 = {10000};


        int[] nums1 = {2, 2};
        int[] nums2 = {1, 3, 4};
        double medianSortedArrays = findMedianSortedArrays(nums1, nums2);
        System.out.println(medianSortedArrays);

    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 1、linklist
        // return LinkList(nums1, nums2);

        // 2、时间复杂度为m*logn
        // return m_logn(nums1, nums2);

        // 3、二分查找 复杂度为log(min(m,n))
        /**
         * 1、规定分割线，中位线 totalLine = (m+n+1)/2
         * 2、第一组的分割线右边第一个位置为 i
         *   第二组的分割线右边第一个位置为 j
         * 3、满足num1[i-1] <= num2[j] && num2[j-1] <= num1[i]
         */

        // min(m,n)
        int[] tem;
        if (nums1.length > nums2.length) {
            tem = nums1;
            nums1 = nums2;
            nums2 = tem;
        }

        int m = nums1.length;
        int n = nums2.length;

        int totalLine = (m + n + 1) / 2;
        int left = 0;
        int right = m;
        int i = 0;
        int j = 0;
        // 循环条件
        // 二分查找到合适的left偏移量
        while (left < right) {
            // 二分查找，此处为取第一个数组中左右指针下标的中位数，决定起始位置
            // 此处+1首先是为了不出现死循环，即left永远小于right的情况
            // left和right最小差距是1，此时下面的计算结果如果不加1会出现i一直=left的情况，而+1之后i才会=right
            // 于是在left=i的时候可以破坏循环条件，其次下标+1还会保证下标不会越界，因为+1之后向上取整，保证了
            // i不会取到0值，即i-1不会小于0
            // 此时i也代表着在一个数组中左边的元素的个数
            i = left + (right - left +1) / 2;
            j = totalLine - i;
            if (nums1[i - 1] > nums2[j]) {
                right = i - 1;
            } else {
                left = i;
            }
        }

        i = left;
        j = totalLine - left;

        // 数组越界
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

        if ((m + n) % 2 == 0) {
            return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2d;
        }
        return Math.max(nums1LeftMax, nums2LeftMax);
    }

    private static double m_logn(int[] nums1, int[] nums2) {
        int[] ints = new int[nums1.length + nums2.length];
        if (ints.length == 0) {
            return 0;
        }
        if (nums1.length == 0) {
            if (nums2.length % 2 == 0) {
                return (nums2[nums2.length / 2 - 1] + nums2[nums2.length / 2]) / 2d;
            }
            return nums2[(nums2.length - 1) / 2];
        }
        if (nums2.length == 0) {
            if (nums1.length % 2 == 0) {
                return (nums1[nums1.length / 2 - 1] + nums1[nums1.length / 2]) / 2d;
            }
            return nums1[(nums1.length - 1) / 2];
        }
        int j = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (; j < nums2.length; j++) {
                if (nums1[i] <= nums2[j]) {
                    ints[i + j] = nums1[i];
                    break;
                }
                ints[i + j] = nums2[j];
            }

            if (j == nums2.length) {
                ints[i + j] = nums1[i];
            } else if (i == nums1.length - 1) {
                for (; j < nums2.length; j++) {
                    ints[i + j + 1] = nums2[j];
                }
            }
        }
        if (ints.length % 2 == 0) {
            return (ints[ints.length / 2 - 1] + ints[ints.length / 2]) / 2d;
        }
        return ints[(ints.length - 1) / 2];
    }

    private static double LinkList(int[] nums1, int[] nums2) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        int[] nums;
        if (nums1.length >= nums2.length) {
            linkedList.addAll(Arrays.stream(nums1).boxed().collect(Collectors.toList()));
            nums = nums2;
        } else {
            linkedList.addAll(Arrays.stream(nums2).boxed().collect(Collectors.toList()));
            nums = nums1;
        }
        linkAdd(nums, linkedList);
        int length = nums1.length + nums2.length;
        if (length % 2 == 0) {
            int middle = length / 2;
            return new BigDecimal((linkedList.get(middle - 1) + linkedList.get(middle))).divide(new BigDecimal(2)).doubleValue();
        } else if (length == 1) {
            return linkedList.get(0);
        } else {
            return linkedList.get((length - 1) / 2);
        }
    }

    private static void linkAdd(int[] nums, LinkedList<Integer> linkedList) {
        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = 0; j < linkedList.size(); j++) {
                if (linkedList.get(j).compareTo(nums[i]) < 0) {
                    if (linkedList.size() == j + 1) {
                        linkedList.addLast(nums[i]);
                    }
                    continue;
                }
                linkedList.add(j, nums[i]);
                break;
            }
        }
    }
}

